import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 剑指 Offer 38. 字符串的排列（与 47 同）
 * https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
 */
public class Solutions_Offer_38 {
    public static void main(String[] args) {
        String s = "abc";  // output: {"abc", "acb", "bac", "bca", "cab", "cba"}
//        String s = "aab";  // output: {"aba", "aab", "baa"}

        String[] result = permutation(s);
        System.out.println(Arrays.toString(result));
    }

    public static String[] permutation(String s) {
        // 空值判断与长度小于 1 的判断
        if (s == null || s.length() < 1) {
            return new String[0];
        }
        List<String> res = new ArrayList<>();
        int len = s.length();
        char[] sarr = s.toCharArray();
        // 对 len 个字符进行排序
        Arrays.sort(sarr);
        // mark[2] = true：标记 sarr[2] 元素已经添加到字符串中（即回溯中）
        boolean[] mark = new boolean[len];

        permutation(res, sarr, mark, new StringBuilder(), len);
        return res.toArray(new String[res.size()]);
    }

    public static void permutation(List<String> res, char[] sarr, boolean[] mark,
                                   StringBuilder sb, int len) {
        // 结束条件
        if (sb.length() == len) {
            // 添加结果集并返回
            res.add(sb.toString());
            return;
        }
        // 每次递归进入时，都从第一个元素开始遍历，保证每个元素都会扫描到
        for (int i = 0; i < len; i++) {
            if (mark[i]) {
                // 已经在字符串中则不使用
                continue;
            }
            // 若当前遍历字符与前一字符相同，且前一字符标记为 false时，跳过当前字符，否则会出现重复结果
            if (i > 0 && sarr[i] == sarr[i - 1] && !mark[i - 1]) {
                // 以 {'a', 'a', 'b'} 为例
                // 第二个 'a' 不能作为字符串的开头使用，因为前面相同的 'a' 已经回溯过一次，再用就是重复
                // 故而判断条件设置为这种情况，第二个 'a' 作为开头时，第一个 'a' 的标记一定是 false
                continue;
            }
            // 当前字符若可以使用，则添加到字符串中，并将当前字符标记为已使用
            sb.append(sarr[i]);
            mark[i] = true;
            // 添加字符后，再次递归
            permutation(res, sarr, mark, sb, len);
            // 递归完成后，移除最后添加的元素，同时还原状态为未使用
            sb.deleteCharAt(sb.length() - 1);
            mark[i] = false;
        }
    }
}
